1. Field of the Invention
The present invention relates to techniques for compressing digital images. More specifically, the present invention relates to a method and apparatus for compressing a digital image, which operates by transforming a digital image into coefficients and then compressing the low-entropy portions of the coefficients while not substantially compressing the high-entropy portions of the coefficients.
2. Related Art
In recent years, the use of high-resolution digital cameras has increased significantly. Unfortunately, storing the high-resolution digital images produced by such cameras requires large amounts of memory. For example, a 4 mega-pixel digital camera requires up to 12 mega-bytes (MB) of memory to store a single raw, uncompressed digital image. Furthermore, transmitting a large digital image across a network requires a substantial amount of time, even when a high-speed broadband Internet connection is used. In order to deal with these problems, image-compression techniques are typically used to reduce the size of a digital image.
In commonly-used transform-based compression techniques, a digital image is transformed, for example, by using a discrete cosine transform (DCT) or a wavelet transform, to convert pixel values in the digital image into transform-domain coefficients. Next, the transform-domain coefficients are quantized by dividing the transform-domain coefficients by a quantizer and rounding the result to the nearest integer. These quantized transform-domain coefficients are then “entropy coded.” Note that it is the entropy coding that actually compresses the data. The purpose of the transform and the quantization operations is to make the image data more amenable to compression by removing redundancies and by presenting a low-entropy data stream to the entropy coder. Some examples of transform-based image coding techniques are JPEG, which uses a DCT, and JPEG2000, which uses a wavelet transform.
A corresponding decoder performs the inverse operations in reverse order to recover the image. For example, the decoding process can involve entropy decoding, followed by de-quantization and an inverse transform.
In order to produce the best possible compression, modern wavelet-based compression systems use arithmetic coders for entropy coding. An arithmetic coder is an entropy coder that can compress data close to the theoretical maximum that can be achieved (i.e. the length of an arithmetically-coded stream will be close to the entropy of the stream). Since the success of arithmetic-coding depends on the availability of a good probabilistic model of the coefficient bit patterns, highly sophisticated bit-modeling techniques have been developed. One example of a coefficient bit-modeling/arithmetic-coding scheme is EBCOT (Embedded Block Coding with Optimized Truncation), which is incorporated into the JPEG2000 image coding standard.
Although bit-modeling/arithmetic-coding schemes provide good compression, they tend to be slow, even on modern processors. The majority of the time spent decompressing/compressing an image is spent on the coding of the wavelet coefficients. For example, up to 70% of the time taken to decompress a JPEG2000 stream is spent in entropy coding. This large amount of computational time is a substantial obstacle in the deployment of wavelet-based compression techniques for many image-processing applications, the most notable being video applications.
One solution to this problem is to bypass the arithmetic coder. The JPEG2000 standard provides an arithmetic bypass mode, in which the arithmetic coder is bypassed for some of the sub-bitplane passes. Unfortunately, this technique is still extremely complex because: (1) there is at least one pass in each plane that is arithmetically coded, and (2) the bit modeling is performed for all passes regardless of whether the arithmetic coder is to be employed or not.
Another solution is to use the existing JPEG compression standard, which uses DCT and Huffman coding, and has low complexity. Unfortunately, JPEG compression cannot achieve compression comparable to wavelet-based systems. For example, a typical JPEG2000 image is about 30% smaller than a JPEG image of comparable quality. Furthermore, at low quality the blocking artifacts of JPEG are very significant. Note that the entropy coder used for JPEG compression does not attempt to separate the low-entropy and high-entropy portions of the quantized DCT coefficients.
Hence, what is needed is a method and an apparatus for compressing a digital image without the problems described above.